class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

class MyLinkedList {

  constructor() {
    this.size = 0;
  }

  insert(index, data) {
    if (index < 0 || index > this.size) {
      throw new Error("over link node range!");
    }

    const insertedNode = new Node(data);

    if (this.size == 0) {
      this.head = insertedNode;
      this.last = insertedNode;
    } else if (index == 0) {
      insertedNode.next = this.head;
      this.head = insertedNode;
    } else if (this.size == index) {
      this.last.next = insertedNode;
      this.last = insertedNode;
    } else {
      const prevNode = this.get(index - 1);
      insertedNode.next = prevNode.next;
      prevNode.next = insertedNode;
    }

    this.size += 1;
  }

  remove(index) {
    if (index < 0 || index >= this.size) {
      throw new Error("over link node range");
    }
    let removedNode = null;
    if (index == 0) {
      removedNode = this.head;
      this.head = this.head.next;
    } else if (index == this.size - 1) {
      const prevNode = this.get(index - 1);
      removedNode = prevNode.next;
      prevNode.next = null;
      this.last = prevNode;
    } else {
      const prevNode = this.get(index - 1);
      const nextNode = prevNode.next.next;
      removedNode = prevNode.next;
      prevNode.next = nextNode;
    }
    this.size -= 1;
    return removedNode;
  }

  get(index) {
    if (index < 0 || index >= this.size) {
      throw new Error("over link node range!");
    }
    let temp = this.head;
    for (let i = 0; i < index; i += 1) {
      temp = temp.next;
    }
    return temp;
  }

  output() {
    let temp = this.head;
    while (temp != null) {
      console.log(temp.data);
      temp = temp.next;
    }
  }
}

const myLinkedList = new MyLinkedList();
myLinkedList.insert(0, 3);
myLinkedList.insert(0, 4);
myLinkedList.insert(2, 9);
myLinkedList.insert(3, 5);
myLinkedList.insert(1, 6);
myLinkedList.remove(0);
myLinkedList.output();
